DROPS

Document

DOI: 10.4230/LIPIcs.CP.2021.55

Parallelizing a SAT-Based Product Configurator

Authors: Nils Merlin Ullmann, Tomáš Balyo, and Michael Klein

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract

This paper presents how state-of-the-art parallel algorithms designed to solve the Satisfiability (SAT) problem can be applied in the domain of product configuration. During an interactive configuration process, a user selects features step-by-step to find a suitable configuration that fulfills his desires and the set of product constraints. A configuration system can be used to guide the user through the process by validating the selections and providing feedback. Each validation of a user selection is formulated as a SAT problem. Furthermore, an optimization problem is identified to find solutions with the minimum amount of changes compared to the previous configuration. Another additional constraint is deterministic computation, which is not trivial to achieve in well performing parallel SAT solvers. In the paper we propose five new deterministic parallel algorithms and experimentally compare them. Experiments show that reasonable speedups are achieved by using multiple threads over the sequential counterpart.

Cite as

Nils Merlin Ullmann, Tomáš Balyo, and Michael Klein. Parallelizing a SAT-Based Product Configurator. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ullmann_et_al:LIPIcs.CP.2021.55,
  author =	{Ullmann, Nils Merlin and Balyo, Tom\'{a}\v{s} and Klein, Michael},
  title =	{{Parallelizing a SAT-Based Product Configurator}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.55},
  URN =		{urn:nbn:de:0030-drops-153464},
  doi =		{10.4230/LIPIcs.CP.2021.55},
  annote =	{Keywords: Configuration, Satisfiability, Parallel}
}

Document

DOI: 10.4230/DagSemProc.04441.5

04441 Working Group – Description and Matching of Services in Mobile Environments

Authors: Johannes Grünbauer, Michael Klein, Georgia Koloniari, George Samaras, and Can Türker

Published in: Dagstuhl Seminar Proceedings, Volume 4441, Mobile Information Management (2005)

Abstract

Service oriented computing is a new paradigm that is especially interesting in mobile environments. As a characteristics, functionality is hidden behind an interface and described as a black box with the help of a service description lan- guage. This enables participants of the network to enlarge the limited capabilities of their devices by using services provided by others. As service requestors and providers are not fixedly tied together but are dynamically matched and bound, this architecture is especially advantageous in mobile environments and their constantly changing situation

Cite as

Johannes Grünbauer, Michael Klein, Georgia Koloniari, George Samaras, and Can Türker. 04441 Working Group – Description and Matching of Services in Mobile Environments. In Mobile Information Management. Dagstuhl Seminar Proceedings, Volume 4441, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{grunbauer_et_al:DagSemProc.04441.5,
  author =	{Gr\"{u}nbauer, Johannes and Klein, Michael and Koloniari, Georgia and Samaras, George and T\"{u}rker, Can},
  title =	{{04441 Working Group – Description and Matching of Services in Mobile Environments}},
  booktitle =	{Mobile Information Management},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4441},
  editor =	{Margaret H. Dunham and Birgitta K\"{o}nig-Ries and Evaggelia Pitoura and Peter Reiher and Can T\"{u}rker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04441.5},
  URN =		{urn:nbn:de:0030-drops-1672},
  doi =		{10.4230/DagSemProc.04441.5},
  annote =	{Keywords: Service Description , Mobile Environment}
}

Search Results

Documents authored by Klein, Michael

Parallelizing a SAT-Based Product Configurator

Abstract

Cite as

04441 Working Group – Description and Matching of Services in Mobile Environments

Abstract

Cite as

Thanks for your feedback!

Could not send message